//
// Created by ASUS on 2024/3/1.
//
/*
Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 destination 。
指令 用字符串表示，其中每个字符：
'H' ，意味着水平向右移动
'V' ，意味着竖直向下移动
能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是 (2, 3)，"HHHVV" 和 "HVHVH" 都是有效 指令 。
然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k  的编号 从 1 开始 。
给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。
 */

#include <bits/stdc++.h>
using namespace std;

const int MX = 30;
int c[MX][MX];
int init = []() {
	for (int i = 0; i < MX; i++) {
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; j++)
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; // 预处理组合数
	}
	return 0;
}();

string kthSmallestPath(vector<int>& d, int k) {
	int h=d[1],v=d[0];
	string ans;
	for (int i = 0;i < d[0]+d[1]; ++i) {
		if (h > 0) {
			int o = c[h + v - 1][h - 1];
			if (k > o) {
				ans += 'V';
				--v;
				k -= o;
			}else {
				ans += 'H';
				--h;
			}
		}else {
			ans += 'V';
			--v;
		}
	}
	return ans;
}